package leetcode.year2021.month10;

import java.util.LinkedList;

public class _31_02MinStack155 {
  private ListNode dummy = new ListNode(-1);
  private ListNode minNode;

  public _31_02MinStack155() {
  }

  public void push(int val) {
    ListNode valNode = new ListNode(val);
    ListNode tempHead = dummy.next;
    dummy.next = valNode;
    valNode.next = tempHead;
    if (minNode == null || valNode.val < minNode.val){
      minNode = valNode;
    }
  }

  public void pop() {
    if (dummy.next == null){
      return;
    }
    if (dummy.next.next == null){
      dummy.next = null;
      minNode = null;
      return;
    }
    if (dummy.next == minNode){
      minNode = dummy.next.next;
      ListNode prev = minNode;
      while (prev.next != null){
        if (prev.next.val < minNode.val){
          minNode = prev.next;
        }
        prev = prev.next;
      }
      dummy.next = dummy.next.next;
    } else {
      dummy.next = dummy.next.next;
    }
  }

  public int top() {
    if (dummy.next == null){
      return 0;
    }
    return dummy.next.val;
  }

  public int getMin() {
    return minNode.val;
  }

  public class ListNode{
    public int val;
    public ListNode next;
    public ListNode head;

    public ListNode(int val) {
      this.val = val;
    }
  }
  /**
   * 155. 最小栈
   * 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
   *
   * push(x) —— 将元素 x 推入栈中。
   * pop() —— 删除栈顶的元素。
   * top() —— 获取栈顶元素。
   * getMin() —— 检索栈中的最小元素。
   *
   *
   * 示例:
   *
   * 输入：
   * ["MinStack","push","push","push","getMin","pop","top","getMin"]
   * [[],[-2],[0],[-3],[],[],[],[]]
   *
   * 输出：
   * [null,null,null,null,-3,null,0,-2]
   *
   * 解释：
   * MinStack minStack = new MinStack();
   * minStack.push(-2);
   * minStack.push(0);
   * minStack.push(-3);
   * minStack.getMin();   --> 返回 -3.
   * minStack.pop();
   * minStack.top();      --> 返回 0.
   * minStack.getMin();   --> 返回 -2.
   *
   *
   * 提示：
   *
   * pop、top 和 getMin 操作总是在 非空栈 上调用。
   */
}
